import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class 单词接龙 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 建立哈希表
        Set<String> dict = new HashSet<>(wordList); // 总的所有的词
        Set<String> smallLevel = new HashSet<>(); // 个数少的扩展
        Set<String> bigLevel = new HashSet<>(); // 个数大的先不扩展
        Set<String> nextLevel = new HashSet<>(); // 个数少的开始扩展
        // 不存在 endWord 元素一定无法转变
        if (!dict.contains(endWord)) {
            return 0;
        }
        smallLevel.add(beginWord);
        bigLevel.add(endWord);
        // 最开始是两层, 如果一次变换就成功就是两层
        for (int len = 2; !smallLevel.isEmpty() ; len++) {
            // 扩展小的层级
            for (String s :smallLevel) {
                // 转换成字符数组
                char[] word = s.toCharArray();
                // 遍历所有的位数
                for (int i = 0; i < word.length; i++) {
                    // 老的记录一下, 防止重复遍历
                    char old = word[i];
                    // a - z 字符都填一遍
                    for (char j = 'a'; j <= 'z'; j++) {
                        // 如果不是和最开始的字符串重复, 先转化成字符串
                        if (old != j) {
                            word[i] = j;
                            String next = String.valueOf(word);
                            // 大的层级存在, 直接返回 len
                            if (bigLevel.contains(next)) {
                                return len;
                            }
                            // 总字典表存在这个, 添加到 nextLevel 里面, dict里面删除防止之后重复遍历
                            if (dict.contains(next)) {
                                dict.remove(next);
                                nextLevel.add(next);
                            }
                        }
                    }
                    // 修改回原来的字符, 因为每次只修改一位
                    word[i] = old;
                }
            }
            // 如果扩展出来的大小还是没有 bigLevel 大的话, 把nextLevel继续当成smallLevel
            if (nextLevel.size() <= bigLevel.size()) {
                Set<String> tmp = smallLevel;
                smallLevel = nextLevel;
                nextLevel = tmp;
            } else {
                // 扩展出来比上一次更大, 把 nextLevel 当成 bigLevel
                // smallLevel 里面换成原来的 bigLevel
                Set<String> tmp = smallLevel;
                smallLevel = bigLevel;
                bigLevel = nextLevel;
                nextLevel = tmp;
            }
            nextLevel.clear();
        }
        return 0;
    }

}
